package class03;

/*
 * 题目描述：
 * 给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
 * 
 * 示例：
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * 
 * 输入: s = "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * 
 * 解题思路：
 * 使用滑动窗口的思想，结合动态规划方法。
 * 用一个数组记录每个字符最近一次出现的位置，然后遍历字符串，
 * 对每个位置计算以该位置结尾的最长无重复字符子串长度。
 * 
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
 */
// 本题测试链接 : https://leetcode.com/problems/longest-substring-without-repeating-characters/
public class Code01_LongestSubstringWithoutRepeatingCharacters {

	public static int lengthOfLongestSubstring(String s) {
		if (s == null || s.equals("")) {
			return 0;
		}
		char[] str = s.toCharArray();
		// 用数组模拟哈希表，记录每个字符最近一次出现的位置
		// 数组大小为256，可以覆盖所有ASCII字符
		int[] map = new int[256];
		// 初始化所有字符的位置为-1，表示尚未出现过
		for (int i = 0; i < 256; i++) {
			map[i] = -1;
		}
		// 记录第一个字符的位置
		map[str[0]] = 0;
		int N = str.length;
		// 最长无重复字符子串的长度
		int ans = 1;
		// 以当前位置结尾的无重复字符子串长度
		int pre = 1;
		// 从第二个字符开始遍历
		for (int i = 1; i < N; i++) {
			// 计算以当前位置结尾的无重复字符子串长度
			// 1. i - map[str[i]]：当前位置到字符上次出现位置的距离
			// 2. pre + 1：前一个位置的长度加1
			// 取两者的最小值
			pre = Math.min(i - map[str[i]], pre + 1);
			// 更新最长长度
			ans = Math.max(ans, pre);
			// 更新当前字符的位置
			map[str[i]] = i;
		}
		return ans;
	}

}